/*
【题目】
给定数组 arr 和整数 num,共返回有多少个子数组满足如下情况:
max(arr[i..j]) - min(arr[i..j]) <= num
max(arr[i..j])表示子数组 arr[i..j]中的最大值,min(arr[i..j])表示子数组 arr[i..j]中的最小值。
【要求】
如果数组长度为 N,请实现时间复杂度为 O(N)的解法。
 */
/**
 *
 * @param {number[]} arr
 * @param {number} num
 * @return {number}
 */
function getSubArrCounts (arr, num) {
  let L = 0
  let R = 0
  const maxQueue = []
  const minQueue = []
  let counts = 0
  while (L < arr.length) {
    while (R < arr.length) {
      while (maxQueue.length && arr[maxQueue[maxQueue.length - 1]] <= arr[R]) {
        maxQueue.pop()
      }
      maxQueue.push(R)
      while (minQueue.length && arr[minQueue[minQueue.length - 1]] >= arr[R]) {
        minQueue.pop()
      }
      minQueue.push(R)

      if (maxQueue[0] - minQueue[0] > num) {
        break
      }
      R++
    }
    if (maxQueue[0] === L) {
      maxQueue.shift()
    }
    if (minQueue[0] === L) {
      minQueue.shift()
    }
    counts += R - L
    L++
  }
  return counts
}

console.log(getSubArrCounts([1, 2, 3, 4, 5], 2))
